
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0074
 * @Author : WangRuoyu 
 * @Date : 2023/9/14 16:11
 */

#include "iostream"
#include "vector"

using namespace std;

//class Solution {
//public:
//    bool searchMatrix(vector<vector<int>> &matrix, int target) {
//        const int M = matrix.size();
//        const int N = matrix[0].size();
//
//        int l = 0;
//        int r = M - 1;
//
//        int x;
//
//        if (target >= matrix[M - 1][0]) {
//            x = M - 1;
//        } else {
//            while (l < r) {
//                int mid = l + r >> 1;
//                if (matrix[mid][0] > target) r = mid;
//                else l = mid + 1;
//            }
//
//            if (l == 0) return false;
//
//            x = l-1;
//
//        }
//
//        l = 0, r = N - 1;
//
//        while (l < r) {
//            int mid = l + r >> 1;
//            if (matrix[x][mid] >= target) r = mid;
//            else l = mid + 1;
//        }
//
//        return matrix[x][l] == target;
//    }
//};

class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        const int M = matrix.size();
        const int N = matrix[0].size();

        int l = 0;
        int r = N * M - 1;


        while (l < r) {
            int mid = l + r >> 1;
            if (matrix[mid / N][mid % N] >= target) r = mid;
            else l = mid + 1;
        }

        return matrix[l / N][l % N] == target;
    }
};

int main() {
    Solution sl;
    vector<vector<int>> matrix = {{1,  3,  5,  7},
                                  {10, 11, 16, 20},
                                  {23, 30, 34, 60}};
    int target = 3;
    printf("%d", sl.searchMatrix(matrix, target));
    return 0;
}